﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;



    public class ConvexHullAlgorithm
    {
        public static void Main()
        {
            // 1. find the point with lowest y coordinate 
            // (if equal, then by lowest x coordinate). This is the pivot point
            // 2. sort the points in increasing order of the angle
            // they make with the X-axis
            // 3. for every 2 other points calculate the cross vector product
            // with the pivot point 
            // if it is a left turn -> move to the next point
            // if it is a right turn -> remove the top point
            // cross product == 0 the points are colinear
            // cross product > 0 -> left turn
            // cross product < 0 -> right turn

            //using Graham
            //http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull.cpp
            //http://softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm
            List<Point> points = new List<Point>()
            {
                new Point(60, 50),
                new Point(100, 30),
                new Point(40, 40),
                new Point(20, 70),
                new Point(50, 20),
                new Point(30, 70),
                new Point(10, 10),
                new Point(110, 70),
                new Point(90, 60),
                new Point(80, 20),
                new Point(70, 80),
                //new Point(20, 20),

                new Point(20, 30),

                new Point(30, 60),
            };

            int startingPointIndex = FindStartingPointIndex(points);
            SwapPoints(points, startingPointIndex, 0);


            SortPointsByPolarAngle(points);


            //PrintPoints(points);
            List<Point> convexHull = FindConvexHull(points);
            //List<Point> convexHull2 = FindConvexHullWithStack(points);
            PrintPoints(convexHull);
            Console.WriteLine("WITH STACK");
            //PrintPoints(convexHull2);
        }

        private static void SortPointsByPolarAngle(List<Point> points)
        {
            Point pivotPoint = points[0];
            PointComparer pointComparer = new PointComparer(pivotPoint);
            points.Sort(1, points.Count - 1, pointComparer);
            points.Reverse(1, points.Count - 1);
        }

        public static int FindStartingPointIndex(List<Point> points)
        {
            int startingPointIndex = 0;
            for (int i = 1; i < points.Count; i++)
            {
                if ((points[startingPointIndex].Y > points[i].Y) ||
                    ((points[startingPointIndex].Y == points[i].Y) && (points[startingPointIndex].Y > points[i].X)))
                {
                    startingPointIndex = i;
                }
            }
            return startingPointIndex;
        }

        public static void SwapPoints(List<Point> points, int firstPointIndex, int secondPointIndex)
        {
            Point swappingPoint = points[firstPointIndex];
            points[firstPointIndex] = points[secondPointIndex] ;
            points[secondPointIndex] = swappingPoint; 
        }

        public static List<Point> FindConvexHull(List<Point> points)
        {
            Point[] hull = new Point[points.Count];
            int hsize = 0;

            //stack -> i = 3
            for (int i = 0; i < points.Count; i++)
            {
                while (hsize >= 2 && 
                    Point.CalculateCrossProduct(
                    hull[hsize - 2], hull[hsize - 1], points[i]) < 0)
                {
                    hsize--;
                }
                
                hull[hsize] = points[i];
                hsize++;
            }
            //hull[hsize] = points[0];
            return hull.ToList();
        }

        public static List<Point> FindConvexHullWithStack(List<Point> points)
        {
            Stack<Point> convexHull = new Stack<Point>();

            //convexHull.Push(new Point(0, 0));

            Point[] hull = new Point[points.Count];
            int hsize = 0;

            //stack -> i = 3
            for (int i = 0; i < points.Count; i++)
            {
                //while (hsize >= 2 &&
                //    Point.CalculateCrossProduct(
                //    hull[hsize - 2], hull[hsize - 1], points[i]) < 0)
                //{
                //    --hsize;
                //}
                //hull[hsize++] = points[i];
                Point pivotPoint = points[i];

                while (convexHull.Count >= 2 &&
                    Point.CalculateCrossProduct(
                    convexHull.Peek(), convexHull.ElementAt(
                        convexHull.Count - 2), points[i]) < 0)
                {
                    convexHull.Pop();

                }
                convexHull.Push(pivotPoint);
            }

            //return convexHull;
            return convexHull.ToList();
        }

        public static void PrintPoints(List<Point> points)
        {
            Console.WriteLine("Printing");
            for (int i = 0; i < points.Count - 5; i++)
            {
                if (points[i] != null)
                {
                    Console.WriteLine(points[i]);
                }
                
            }
        }

        
    }

